import java.util.*;

/**
 * 剑指 Offer 32 - III. 从上到下打印二叉树 III
 * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 */
public class Solutions_Offer_32_III {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> result = levelOrder2(root);
        System.out.println(result);
    }

    // 广度优先搜索
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // flag = true，说明当前遍历的层是二叉树中的奇数层（根节点为奇数层），从而正序打印
        boolean flag = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            Integer[] arr = new Integer[size];
            // 循环将该层上的节点对象，弹出队列并进行结果集记录与不为 null 的左右子节点入队的操作
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (flag) {
                    arr[i] = node.val;
                } else {
                    // 倒序打印
                    arr[size - 1 - i] = node.val;
                }
                // 左右子节点对象，若不为 null 则入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 当前层为奇数层，下一层则为偶数层
            flag = !flag;
            res.add(Arrays.asList(arr));
        }
        return res;
    }

    // 深度优先搜索
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelOrder_dfs(root, 0, res);
        return res;
    }

    public static void levelOrder_dfs(TreeNode root, int level,
                                                     List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        if (level >= res.size()) {
            res.add(new ArrayList<>());
        }
        if (level % 2 == 0) {
            // 正序
            res.get(level).add(root.val);
        } else {
            // 倒序
            res.get(level).add(0, root.val);
        }
        // 递归进入左右子树
        levelOrder_dfs(root.left, level + 1, res);
        levelOrder_dfs(root.right, level + 1, res);
    }
}
